/*
COPYRIGHT NOTICE: This software is provided by Canada Post Corporation (CPC). 
It can be used for postal ID-tag applications only. The software may be 
freely distributed and/or modified.  A condition of such distribution is that 
this copyright notice is always included in the comments heading the software. 
This software is licensed "as is" without any other warranty of any kind. 
CPC expressly disclaims all warranties or conditions including, but not 
limited to, implied warranties or conditions of merchantability and fitness 
for particular purpose and those arising by statute or otherwise in law or 
from course of dealing or usage of trade. In no event shall CPC be liable 
for any direct, indirect, special, incidental, consequential or other damages 
arising out of this software even if CPC has been advised of the possibility 
of such damages in advance.
*/
/* $Id$ */
/* $Log$ */
/* REED-SOLOMON DECODER FOR 0-1 CODES OVER GF(23).
Description: This program receives a 78-bit string of {0,1} representing the 
encoded data with parity symbols and start/stop bits as the input and generates 
a 56 bit string of {0,1} representing the encoded data as the output.

The input consists of a start bit, 14 four bit data symbols in the range 0-15 
followed by 4 five bit parity symbols which are encoded using a lookup table 
which restricts run lengths of consecutive zeros, and a stop bit. Since the 
Reed-Solomon code is defined over the field of 23 elements, parity symbols in 
the range 23-31 indicate that the symbol is in error.

Error and erasure decoding of the Reed-Solomon codeword is achieved via the 
Euclidean algorithm (see Clark and Cain for the actual algorithm).  Erased bits 
are indicated in the received codeword by the bit value 4.

The output is 56 (14x4) data bits.
*/
static char rcsid[] = "$Id$";
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#include <sys/types.h>
#include <time.h>

#include "common.h"
#include "decode23.h"

/* Define data type for small integers. */
#define INT8 unsigned char
#define SINT8 char
#define BOOLEAN char
const INT8 n = 18;     /* total number of symbols */
const INT8 k = 14;     /* number of 4 bit data symbols */
const INT8 n_k = 4;    /* n - k */
const INT8 n_1 = 17;   /* n - 1 */
const INT8 t = 2;      /* n - k divided by 2 */
const INT8 t2_1 = 3;   /* t2 - 1 */
const INT8 prime = 23;
/* Global definitions and prototypes for decode23 */
#define MIDLEN 65
#define MAXLEN 88
#define LENGTH 78 
#define PADLEN 94
const INT8 alog[23] = {
    1,  5,  2, 10,  4, 20,  8, 17, 16, 11,  9, 22,
   18, 21, 13, 19,  3, 15,  6,  7, 12, 14,  1
};
const INT8 inv[23] = {
    0,  1, 12,  8,  6, 14,  4, 10,  3, 18,  7, 21,
    2, 16,  5, 20, 13, 19,  9, 17, 15, 11, 22
};
const INT8 lookup[32] = {
   64, 64, 64, 64, 64, 64, 64, 64, 22, 21, 20, 19, 18, 17, 16, 15,
   64, 13, 12, 11, 10,  9,  8,  7, 14,  6,  5,  4,  3,  2,  1,  0
};
/* function prototypes */
int convert (int month, int binary[], int codeword[], int v[]);
int decode (int codeword[], int v[], int degv);
int preprocess (int n, int b[], int c[], int month, int *tries, int maxtries);
int validate (int c[], int prescan, int month);
void make_out_data (int codeword[], char output[]);
int checksum (int b[], int c[]);
/* main program */
void main (int argc, char *argv[])
{  
  int i,j;
  FILE *fd;
  int nline;
  int binary[100];
  int codeword[18];
  BOOLEAN output_stats = 0;
  struct tm *current_date_and_time;
  int nbar, tries, maxtries = 99;
  int checkdate = 1;
  char output[56];
  char buf[100];
  char *cp;
  time_t q;

#ifdef TURBOC
  clock_t start, end;
#endif
cp = NULL;
  for (i = 1; i < argc; i++) 
    if (strcmp(argv[i],"-s") == 0) 
      ++output_stats;
else if (strcmp(argv[i],"-d") == 0) 
      checkdate = 0;
    else if (strcmp(argv[i],"-m") == 0) 
      maxtries = atoi(argv[++i]);
    else
      cp = argv[i];
  if (cp == NULL) {
     fprintf(stderr, "ERROR - No filename specified.\n");
     exit(1);
  }
  if (maxtries <= 0) maxtries = 1;
  if ((fd = fopen (cp, "r")) == NULL) {
     fprintf (stderr, "Unable to open input file %s.\n", cp);
     exit(1);
  }
  nline = 0;
#ifdef TURBOC
  start = clock ();
#endif

  if (checkdate && time(&q)) {
     current_date_and_time = gmtime(&q);
     if (current_date_and_time != NULL) 
       checkdate = current_date_and_time->tm_mon + 1;
  } else {
     checkdate = 0;
  }
   
  while (fgets (buf, sizeof (buf), fd)) {
     ++nline;
     nbar = strlen (buf);
     while ((nbar > 0) && (buf[nbar-1] == '\n' || buf[nbar-1] == '\r' || buf[nbar-1] == ' '))
       nbar = nbar - 1;
     while ((nbar > 0) && (buf[nbar-1] == '0' || buf[nbar-1] == '4'))
       nbar = nbar - 1;
     j = 0;
     while ((nbar > 0) && (buf[j] == '0' || buf[j] == '4')) {
	nbar = nbar - 1;
	j++;
     }
     nbar = nbar < MAXLEN ? nbar : MAXLEN;
     if (nbar == 0) continue; /* skip blank lines - no error message */
     for (i = 0; i < nbar; i++) {
        if (buf[i+j] != '0' && buf[i+j] != '1' && buf[i+j] != '4') {
           fprintf (stderr, "ERROR - Invalid input at line %d.\n", nline);
           fprintf (stderr, "        Invalid character at position %d.\n", i+j);
           exit (1);
        } else {
           binary[i] = buf[i+j] - '0';
        }
     }
     tries = 0;
     if (preprocess(nbar, binary, codeword, checkdate, &tries, maxtries) == 1) {
        make_out_data(codeword, output);
        printf("%s\n",output);
     }
  }

  }

#ifdef TURBOC
  if (output_stats) {
     end = clock ();
     printf("Total time was %f seconds.\n",(end - start) / CLK_TCK);
  }
#endif
exit(0);
}
void make_out_data (int codeword[], char output[])
{
   int i, j, p;
   p = 0;
   for (i = 0; i < k; i++) 
     for (j = 3; j > -1; j--) 
       if ((codeword[i] >> j) & 1)
         output[p++] = '1';
       else
         output[p++] = '0';
   output[p] = '\0';
}
int checksum (int b[], int c[])
{
   int i, j, p;
   int sum = 0;
   const INT8 lookup[23] = {
      31, 30, 29, 28, 27, 26, 25, 23, 22, 21, 20,
      19, 18, 17, 24, 15, 14, 13, 12, 11, 10,  9,  8
   };
   p = 0;
   for (i = 0; i < k; i++) 
     for (j = 3; j > -1; j--) 
       sum += ((c[i] >> j) & 1) == b[p++];
   for (i = k; i < n; i++) 
     for (j = 4; j > -1; j--) 
       sum += ((lookup[c[i]] >> j) & 1) == b[p++];
   return sum;
}
int validate (int c[], int prescan, int month)
{
   int *F;
   int i, j, l;
   const int unmap[23] = {
      -1, 13, 12, 11, 10, 9, 8, 7, 14, 6, 5, 4, 3, 2, 1, 0,
      -1, -1, -1, -1, -1, -1, -1
   };

return 1;
}
int preprocess (int n, int b[], int c[], int month, int *tries, int maxtries)
{
   int *p;
   int i,j,q,l,m;
   int d[PADLEN];
   int degv, v[5];
   int saved[18];
   int tmp, sum;
   int max;
   q = n;
   if (n == LENGTH) {
     if (b[0] != 1 || b[LENGTH-1] != 1) {
        d[0] = 4;
        for (i = 0; i < n; i++) 
          d[i + 1] = b[i];
        d[n + 1] = 4;
        n += 2;
        p = &d[0];
     } else {
        p = &b[0];
     }
  }
   j = 0;
   m = 1;
   l = n - LENGTH + 1;
   if (q < MIDLEN) 
     j = l - 1;
   else if (q < LENGTH)
     m = l - 1;
   sum = 0;
   max = 0;
   for (i = j; i < l; i += m) {
      if (p[i] != 1) continue;
      ++*tries;
      if ((degv = convert(month, &p[i+1], c, v)) < n_k)
	if (decode(c, v, degv))
	  if (validate(c,0,month)) {
	     tmp = checksum(&p[i+1], c);
	     if (tmp > max) {
		sum = tmp;
		max = tmp;
		for (q = 0; q < 18; q++)
		  saved[q] = c[q];
	     };
	  }
   }
   if (sum) {
      for (i = 0; i < 18; i++) 
	c[i] = saved[i];
      return 1;
   }
}
int convert (int month, int binary[], int codeword[], int v[])
{
  int i, j, z, w, temp;
  int erase, degv;
/* Convert the received codeword from binary to GF(23) symbols. */
  for (i = 0; i < k; i++) {
    temp = 0;
    if (binary[4 * i + 0] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * i + 1] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * i + 2] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * i + 3] == 1)
      temp ^= 1;
    codeword[i] = temp;
  }
/* Next we convert the parity symbols. */
  for (i = 0; i < n_k; i++) {
    temp = 0;
    if (binary[4 * k + 5 * i + 0] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * k + 5 * i + 1] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * k + 5 * i + 2] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * k + 5 * i + 3] == 1)
      temp ^= 1;
    temp <<= 1;
    if (binary[4 * k + 5 * i + 4] == 1)
      temp ^= 1;
    codeword[i + k] = lookup[temp];
  }
  degv = 0;
  v[0] = 1;
  for (i = 1; i <= n_k; i++)
    v[i] = 0;
  for (i = 0; i < n_k; i++) { 
    if (codeword[i + k] < 64) {
       erase = 0;
       if (binary[4 * k + 5 * i + 0] == 4) erase |= 1;
       if (binary[4 * k + 5 * i + 1] == 4) erase |= 1;
       if (binary[4 * k + 5 * i + 2] == 4) erase |= 1;
       if (binary[4 * k + 5 * i + 3] == 4) erase |= 1;
       if (binary[4 * k + 5 * i + 4] == 4) erase |= 1;
       if (erase) codeword[i + k] = 0;
    } else {
       erase = 1;
       codeword[i + k] = 0;
    }
    if (erase != 0) {
      if (++degv > n_k) {
         return degv;
      }
      w = alog[n_k - i - 1];
      for (j = degv; j > 0; j--)
        v[j] = (v[j] - w * v[j - 1]) % prime;
    }
  }
  for (i = 0; i < k; i++) {
    if (codeword[i] < 64) {
       erase = 0;
       if (binary[4 * i + 0] == 4) erase |= 1;
       if (binary[4 * i + 1] == 4) erase |= 1;
       if (binary[4 * i + 2] == 4) erase |= 1;
       if (binary[4 * i + 3] == 4) erase |= 1;
       if (erase) codeword[i] = 0;
    } else {
       erase = 1;
       codeword[i] = 0;
    }
    if (erase != 0) {
      if (++degv > n_k) {
         return degv;
      }
      w = alog[n - i - 1];
      for (j = degv; j > 0; j--)
        v[j] = (v[j] - w * v[j - 1]) % prime;
    }
  }
/* Make sure the erasure polynomial is in the range 0-prime-1. */
  for (z = degv; z >= 0; z--) {
    if (v[z] < 0)
      v[z] += prime;
  }
  return degv;
}
/* DECODE
   This function performs the decoding of the Reed-Solomon codeword.
   Decoding is based on the Euclidean algorithm.
   ipress@math.carleton.ca
*/
int decode (int codeword[], int v[], int degv)
{
  int i, j, x, z, tau, r, s, w, temp, bound, alpha;
  int syn[5], a[5], b[5], u[5], dv[5], cor[18];
  int errcount, maxerrs, dega, degb, delta, check;
  errcount = 0;
  maxerrs = degv + (n_k-degv)/2;  /* Maximum number of correctable positions.*/
  for (i = 0, j = n - 1; i <= j; i++, j--) {
     cor[i] = codeword[j];
     cor[j] = codeword[i];
  }
  for (i = n_k; i < n; i++)
    cor[i] ^= 15;
  check = 0;
  for (i = 0; i <= t2_1; i++) {
    x = alog[i + 1];
    s = cor[n_1];
    for (j = n - 2; j >= 0; j--) {
      s = (cor[j] + s * x) % prime;
    }
    syn[i] = s;
    check |= s;
  }
  if (check == 0) {
    return 1;
  }
  syn[n_k] = 0;
  for (i = 0; i <= n_k; i++) {  
    a[i] = u[i] = 0;
    b[i] = syn[i];     
  }
  a[n_k] = 1;
  dega = n_k;
  for (j = 0; j < n_k; j++)
    for (i = 1; i <= j; i++)
      b[j] = (b[j] + v[i] * syn[j - i]) % prime;
  for (degb = n_k - 1; b[degb] == 0 && degb > 0; degb--);
  bound = t + (degv >> 1); 
  while (degb >= bound) {
    delta = dega - degb;
    w = inv[b[degb]];
    for (z = 0; z <= delta; z++) {
      tau = prime - (a[dega - z] * w) % prime;
      for (i = 0; i <= degb; i++) {
        a[delta - z + i] = (a[delta - z + i] + b[i] * tau) % prime;
        u[delta - z + i] = (u[delta - z + i] + v[i] * tau) % prime;
      }
    }
    for (j = 0; j <= dega; j++) {
      temp = a[j];
      a[j] = b[j];
      b[j] = temp;
    }
    for (j = 0; j <= n_k; j++) {
      temp = u[j];
      u[j] = v[j];
      v[j] = temp;
    }
    dega = degb;
    for (degb = degb - 1; b[degb] == 0 && degb > 0; degb--);
    degv += delta;
  }
  for (i = 0; i < degv; i++)
    dv[i] = ((i + 1) * v[i + 1]) % prime;
  for (i = 0; i < n; i++) {
    alpha = alog[i];
    w = inv[alpha];
    s = v[degv];
    for (j = degv - 1; j >= 0; j--) {
      s = (s * w + v[j]) % prime;
    }
    if (s == 0) {    
      errcount++;
      r = dv[degv - 1];
      for (j = degv - 2; j >= 0; j--)
        r = (r * w + dv[j]) % prime;
      temp = b[degb];
      for (j = degb - 1; j >= 0; j--)
        temp = (temp * w + b[j]) % prime;
      cor[i] = (cor[i] + temp * inv[r]) % prime;
    }
  }
  if (errcount == degv && errcount <= maxerrs) {
     for (i = 0, j = n - 1; i <= j; i++, j--) { 
	codeword[i] = cor[j];
	codeword[j] = cor[i];
     }
     for (i = 0; i < k; i++) 
       codeword[i] ^= 15;
    return 1;
  }
}
